// errsaver.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <string.h>
#include <malloc.h>
#include <stdarg.h>
#include <list>
#include <iostream>
#include <AtlStr.h>
//#include "C:\MARUS\MyProjects\include\range.h"
//#include "C:\MARUS\MyProjects\include\char_traits.h"
#include <trie.h>

#define strtk_no_tr1_or_boost
#include "./strtk/strtk.hpp"
using namespace ATL;


class prec_timer  
{
private:
	LARGE_INTEGER _start;
	LARGE_INTEGER _stop;

public:
	prec_timer() 
    {
        _stop.QuadPart = _start.QuadPart = 0;
        start();
	}

    static  
	long double to_double(const LARGE_INTEGER& val) throw()
    {
        return (long double( val.u.HighPart) * -1. + val.u.LowPart);

		//long double f = val.u.HighPart;
		//f *= -1.;
		//f += val.u.LowPart;
		//return f;
	}

    static
    double  getFreq() throw()
    {
	    LARGE_INTEGER freq;
        ::QueryPerformanceFrequency(&freq);
        return (to_double(freq));
    }

    static inline
    double  frequency() throw()
    {
        static double freq(getFreq());
        return freq;
    }

	void start() 
    {
        ::QueryPerformanceCounter(&_start);
        _stop.QuadPart = _start.QuadPart;
    }

	void stop() 
    {
        ::QueryPerformanceCounter(&_stop);
	}

    double  duration() const
    {
		return (to_double(_stop) - to_double(_start))/frequency();
    }

    double now()
    {
        stop();
        return (duration());
    }

    double restart()
    {
        double ret(now());
        start();
        return (ret);
    }
};

class scoped_timer
{
private:

    scoped_timer(const scoped_timer&);
    scoped_timer& operator=(const scoped_timer&);

    prec_timer  _timer;
    double&     _value;

public:

    scoped_timer(double& value_)
        : _value(value_)
    {
        _value = 0;
        _timer.start();
    }

    ~scoped_timer()
    {
        _value = _timer.now();
    }

};

struct   _Logical
{
    typedef class _True {char _[1];};
    typedef class _False{char _[2];};
};

template <class _Class, class _Base>
class _Inherits_from : private _Logical
{
	static _True  _Inherits(_Base);
	static _False _Inherits(...);
	static _Class _Make_class();

public:
    static const int Value = (sizeof(_Inherits(_Make_class())) == sizeof(_True));
};


struct  IntCh
{
    int     _ch;
    __forceinline IntCh()
        : _ch(0)
    {}

    template<typename _Ch>
    __forceinline IntCh(register const _Ch ch_)
        : _ch(ChTraits<_Ch>::to_int_type(ch_))
    {}

    __forceinline bool operator<(int rh_) const
    {
       return _ch < rh_;
    }
    __forceinline bool operator==(int rh_) const
    {
       return _ch == rh_;
    }
    __forceinline operator int() const
    {
        return _ch;
    }
    __forceinline operator unsigned int() const
    {
        return (unsigned int)_ch;
    }
};


#define DOALIGN(x,b) (((x) + (b) - 1) & ~((b) - 1))

#ifndef BITS_PER_BYTE
#define BITS_PER_BYTE  8
#endif

#define ALIGN_BITSET_SIZE(set_size, unit_size) DOALIGN((set_size),((unit_size)*BITS_PER_BYTE))

template <unsigned int _Set_size, typename _Storage_t = unsigned __int64>
class   bitset
{
private:
    enum {
        _STORAGE_ITEMS = (ALIGN_BITSET_SIZE(_Set_size, sizeof(_Storage_t))/BITS_PER_BYTE)/sizeof(_Storage_t),
        _BITS_PER_CHUNK = sizeof(_Storage_t)*BITS_PER_BYTE,
        _CHUNK_MASK = _BITS_PER_CHUNK-1
    };

    _Storage_t   _storage[_STORAGE_ITEMS];    
    static inline _Storage_t _bittest(register const _Storage_t* storage_, register unsigned int bit_num) throw()
    {
         return storage_[bit_num / _BITS_PER_CHUNK ] & (1 << (bit_num & _CHUNK_MASK));
    }
    static inline _Storage_t _bittestandset(register _Storage_t* storage_, register unsigned int bit_num) throw()
    {
         _Storage_t& chunk = storage_[bit_num / _BITS_PER_CHUNK ];
         _Storage_t bit = 1 << (bit_num & _CHUNK_MASK);
         _Storage_t ret = chunk & bit;
         chunk |= bit;
         return ret;
    }
    static inline _Storage_t _bittestandreset(register _Storage_t* storage_, register unsigned int bit_num) throw()
    {
         _Storage_t& chunk = storage_[bit_num / _BITS_PER_CHUNK ];
         _Storage_t bit = 1 << (bit_num & _CHUNK_MASK);
         _Storage_t ret = chunk & bit;
         chunk &= ~bit;
         return ret;
    }
    static inline _Storage_t _bittestandcomplement(register _Storage_t* storage_, register unsigned int bit_num) throw()
    {
         _Storage_t& chunk = storage_[bit_num / _BITS_PER_CHUNK ];
         _Storage_t ret = chunk & (1 << (bit_num & _CHUNK_MASK));
         chunk &= ~ret;
         return ret;
    }
    static  __forceinline bool set_bit(register _Storage_t* storage_, register unsigned int bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        return ToBool(_bittestandset(storage_, bit_num_));
    }

    static  __forceinline bool reset_bit(register _Storage_t* storage_, register unsigned int bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        return ToBool(_bittestandreset(storage_, bit_num_));
    }

    static  __forceinline bool get_bit(register const _Storage_t* storage_, register unsigned int bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        return ToBool(_bittest(storage_, bit_num_));
    }

    static  __forceinline bool flip_bit(register _Storage_t* storage_, register unsigned int bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        return ToBool(_bittestandcomplement(storage_, bit_num_));
    }

public:


    __forceinline
    void    clear()
    {
        ::memset(_storage, 0, sizeof(_storage));
    }

    __forceinline
    bitset()
    {
        clear();
    }

    template <typename _Char>
    bitset(const _Char* ptr_)
    {
        init(ptr_);
    }

    __forceinline
    bitset(const bitset& ref_) throw()
    {
        ::memcpy(_storage, ref_._storage, sizeof(_storage));
    }

    bool    empty() const
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            if (_storage[i])
                return false;
        }
        return true;
    }

    __forceinline
    bitset&  operator=(const bitset& ref_) throw()
    {
        ::memcpy(_storage, ref_._storage, sizeof(_storage));
        return (*this);
    }

    bitset&  operator+=(const bitset& ref_) throw()
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            _storage[i] |= ref_._storage[i];
        }
        return (*this);
    }

    bitset&  operator-=(const bitset& ref_) throw()
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            _storage[i] &= ~ref_._storage[i];
        }
        return (*this);
    }

    bitset&  operator&=(const bitset& ref_) throw()
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            _storage[i] &= ref_._storage[i];
        }
        return (*this);
    }

    bitset  operator+(const bitset& ref_) throw()
    {
        return (bitset(*this) += ref_);
    }

    bitset  operator-(const bitset& ref_) throw()
    {
        return (bitset(*this) -= ref_);
    }

    bitset  operator&(const bitset& ref_) throw()
    {
        return (bitset(*this) &= ref_);
    }


    __forceinline
    bool set(const IntCh& ch_) throw()
    {
        if ((unsigned int)ch_ < _Set_size)
        {
            set_bit(_storage, ch_);
            return true;
        }
        return false;
    }

    __forceinline
    bool reset(const IntCh& ch_) throw()
    {
        if (ch_ < _Set_size)
        {
            reset_bit(_storage, ch_);
            return true;
        }
        return false;
    }

    __forceinline
    bool    get(register const IntCh& ch_) const throw()
    {
        if ((unsigned int)ch_ < _Set_size)
        {
            //return _storage[ch_>>5] & (1 << (ch_&31)); 
            return ToBool(_bittest(_storage, ch_)); 
            //return get_bit(_storage, ch_);
        }
        return false;
    }

    template <typename _Char>
    __forceinline
    bool    init (const _Char* ptr_) throw()
    {
        clear();
        return add(ptr_);
    }

    template <typename _Char>
    bool add(const _Char* ptr_) throw()
    {
        while(*ptr_)
            if (!set(*ptr_++))
                return false;
        return true;
    }

    template <typename _Char>
    void    remove(const _Char* ptr_) throw()
    {
        while(*ptr_)
            reset(*ptr_++);
    }

};


template <unsigned int _Set_size>
class   boolset
{
private:
    enum {
        _STORAGE_ITEMS = _Set_size
    };

    bool   _storage[_STORAGE_ITEMS];    

    static  __forceinline void set_bit(register bool* storage_, register long bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        storage_[bit_num_] = true;
    }

    static  __forceinline void reset_bit(register bool* storage_, register long bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        storage_[bit_num_] = false;
    }

    static  __forceinline bool get_bit(register const bool* storage_, register long bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        return storage_[bit_num_];
    }

    static  __forceinline bool flip_bit(register bool* storage_, register long bit_num_) throw()
    {
        _ASSERT(bit_num_ < _Set_size);
        return storage_[bit_num_] = !storage_[bit_num_];
    }

public:


    __forceinline
    void    clear()
    {
        ::memset(_storage, 0, sizeof(_storage));
    }

    __forceinline
    boolset()
    {
        clear();
    }

    template <typename _Char>
    boolset(const _Char* ptr_)
    {
        init(ptr_);
    }

    __forceinline
    boolset(const boolset& ref_) throw()
    {
        ::memcpy(_storage, ref_._storage, sizeof(_storage));
    }

    bool    empty() const
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            if (_storage[i])
                return false;
        }
        return true;
    }

    __forceinline
    boolset&  operator=(const boolset& ref_) throw()
    {
        ::memcpy(_storage, ref_._storage, sizeof(_storage));
        return *this;
    }

    boolset&  operator+=(const boolset& ref_) throw()
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            _storage[i] |= ref_._storage[i];
        }
        return (*this);
    }

    boolset&  operator-=(const boolset& ref_) throw()
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            _storage[i] &= ~ref_._storage[i];
        }
        return (*this);
    }

    boolset&  operator&=(const boolset& ref_) throw()
    {
        for(size_t i = 0; i < _STORAGE_ITEMS; ++i)
        {
            _storage[i] &= ref_._storage[i];
        }
        return (*this);
    }

    boolset  operator+(const boolset& ref_) throw()
    {
        return (boolset(*this) += ref_);
    }

    boolset  operator-(const boolset& ref_) throw()
    {
        return (boolset(*this) -= ref_);
    }

    boolset  operator&(const boolset& ref_) throw()
    {
        return (boolset(*this) &= ref_);
    }


    __forceinline
    bool set(const IntCh& ch_) throw()
    {
        if ((unsigned)ch_ < _Set_size)
        {
            set_bit(_storage, (int)ch_);
            return true;
        }
        return false;
    }

    __forceinline
    bool reset(const IntCh& ch_) throw()
    {
        if (ch_ < _Set_size)
        {
            reset_bit(_storage, ch_);
            return true;
        }
        return false;
    }

    __forceinline
    bool    get(const IntCh& ch_) const throw()
    {
        if ((unsigned int)ch_ < _Set_size)
        {
            return get_bit(_storage, (int)ch_);
        }
        return false;
    }

    template <typename _Char>
    __forceinline
    bool    init (const _Char* ptr_) throw()
    {
        clear();
        return add(ptr_);
    }

    template <typename _Char>
    bool add(const _Char* ptr_) throw()
    {
        while(*ptr_)
            if (!set(*ptr_++))
                return false;
        return true;
    }

    template <typename _Char>
    void    remove(const _Char* ptr_) throw()
    {
        while(*ptr_)
            reset(*ptr_++);
    }

};

typedef boolset<128> ascii_set;

template<class _Ty> 
inline _STD basic_string<_Ty> make_string(const range<const _Ty*>& ref_)
{	// return string composed from range
    return (_STD basic_string<_Ty>(ref_.first, ref_.second));
}

template<class _Ty> 
inline _STD basic_string<_Ty> make_string(const range<_Ty*>& ref_)
{	// return string composed from range
    return (_STD basic_string<_Ty>(ref_.first, ref_.second));
}

template<class _Ty> 
inline range<const _Ty*> make_range(const _STD basic_string<_Ty>& string_)
{	// return range composed from arguments
    return (range<const _Ty*>(string_.data(), string_.data() + string_.length()));
}

template<class _Char> 
typename ChTraits<_Char>::cptr_range get_ident(const typename ChTraits<_Char>::cptr_range& ref_) throw()
{
    ChTraits<_Char>::cptr_range rng(ref_);

    if (!rng.empty() && ChTraits<_Char>::_iscsymf(*(rng.first)))
        while(++rng)
            if (!ChTraits<_Char>::_iscsym(*(rng.first)))
                break;

    return (ChTraits<_Char>::cptr_range(ref_.first, rng.first));
}

template<typename _Derived_t>
class   tokenizer_callback
{
protected:
    inline
    _Derived_t&    get_Derived() throw()
    {
        return *static_cast<_Derived_t*>(this);
    }

    __declspec(property(get=get_Derived))
    _Derived_t&   Derived;

public:
    template<typename _Char>
    inline
    bool operator()(const range<const _Char*>& found_) throw()
    {
        return Derived.ontoken(found_);
    }
};

template <typename value_type, typename _Char>
inline
value_type  make_value(const range<const _Char*>& range_);

template<typename _Char>
inline
_STD    basic_string<_Char> make_value(const range<const _Char*>& range_)
{
    return (::make_string(range_));
}


template<class _Container, class _Inserter = _STD back_insert_iterator<_Container> >
class   fill : public tokenizer_callback< fill<_Container, _Inserter> >
{
public:
    typedef _Inserter   _Myins;
    typedef _Container  _Mycnt;
    typedef typename    _Mycnt::value_type value_type;

protected:
    _Myins    _ins;
public:
    fill(_Mycnt& ref_)
        : _ins(ref_)
    {}

    template <typename _Char>
    inline
    bool ontoken(const range<const _Char*>& found_) throw()
    {
        if (found_)
        {
            _ins = make_value(found_);
        }
        return true;
    }
};

template<typename _Derived_t>
class   predicate_base
{
public:

protected:
    inline
    const _Derived_t&    get_Derived() const throw()
    {
        return *static_cast<const _Derived_t*>(this);
    }

    __declspec(property(get=get_Derived))
    const _Derived_t&   Derived;

    inline  bool    get(const IntCh& ch_) const throw()
    {
        return Derived(ch_);
    }

public:
    template <typename _Char>
    const _Char*    skip(const _Char* ptr_) const throw()
    {
        while(*ptr_ && get(*ptr_))
            ++ptr_;
        return ptr_;
    }

    template <typename _Char>
    const _Char*    skip(const _Char* begin_, const _Char* end_) const throw()
    {
        while(begin_ < end_ && get(*begin_))
            ++begin_;
        return begin_;
    }

    template <typename _Char>
    const _Char*    find(const _Char* ptr_) const throw()
    {
        while(*ptr_ && !get(*ptr_))
            ++ptr_;
        return ptr_; //*ptr_? ptr_: NULL;
    }

    template <typename _Char>
    const _Char*    find(const _Char* begin_, const _Char* end_) const throw()
    {
        while(begin_ < end_ && !get(*begin_))
            ++begin_;
        return begin_;
    }

    template <typename _Char>
    inline
    range<const _Char*> tokenize(range<const _Char*>& range_, bool skip_ = true) const throw()
    {
        range<const _Char*> ret(range_.first);
        ret.second = find(range_.first, range_.second);
        if (skip_)
            range_.first = skip(ret.second, range_.second);
        else
            ++range_;
        return (ret);
    }

    template <typename _Char, typename _Cb>
    inline
    size_t process(_Cb& cb_, range<const _Char*>& range_, bool skip_ = true) const throw()
    {
        size_t ret = 0;
        while(range_)
        {
            range<const _Char*> token = tokenize(range_, skip_);
            cb_(token);
            ++ret;
        }
        return (ret);
    }
};

class  simple_predicate : public predicate_base<simple_predicate>
{
public:
    typedef simple_predicate _Myt;
private:
    _Myt operator=(const _Myt&);

protected:
    IntCh  _value;
public:
    simple_predicate(const IntCh& value_)
        : _value(value_)
    {}

    inline 
    bool operator()(const IntCh& value_) const throw()
    {
        return _value == value_;
    }
};

template <typename _Elem>
class  range_predicate : public predicate_base< range_predicate<_Elem> >
{
public:
    typedef _Elem   value_type;
    typedef const value_type*   const_pointer;
    typedef range<const_pointer>    range_t;

    typedef range_predicate<_Elem> _Myt;
private:
    _Myt operator=(const _Myt&);

protected:
    range_t _range;
public:
    range_predicate(const range_t& range_)
        : _range(range_)
    {}

    range_predicate(const_pointer ptr_)
    {
        _range = ::make_range(_ptr_cch<_Elem>(ptr_));
    }

    inline 
    bool operator()(const IntCh& value_) const throw()
    {
        for(register const_pointer p = _range.first; p < _range.second; ++p) 
            if (IntCh(*p) == value_)
                return true;
        return false;
    }
};

class  bitset_predicate : public predicate_base< bitset_predicate >
                        , public ascii_set
{
public:
    typedef bitset_predicate _Myt;
private:
    _Myt operator=(const _Myt&);

public:
    bitset_predicate()
    {}

    inline
    ascii_set&  operator*()
    {
        return *(ascii_set*)this;
    }

    inline 
    bool operator()(const IntCh& value_) const throw()
    {
        return ascii_set::get(value_);
    }
};

#if 0
class  adaptive_predicate : public predicate_base<adaptive_predicate>
{
protected:

    bool    call(const IntCh& value_);
public:
    template <typename _CharT>
    adaptive_predicate(_CharT ch_)
    {
    }

    template <typename _CharT>
    adaptive_predicate(const _Char* ch_)
    {
    }

    inline 
    bool operator()(const IntCh& value_) const throw()
    {
        return call(value_);
    }
};
#endif
template <typename _Elem, typename Predicate>
class chunker
{
public:
    typedef ChTraits<_Elem>                     Traits;
    typedef typename Traits::const_iterator     Iterator;
    typedef typename Traits::cptr_range         range_type;
    typedef _STD iterator_traits<Iterator>      iterator_traits;

    typedef typename iterator_traits::value_type value_type;
    typedef _STD basic_string<_Elem>    string_type;

    class chunk_iterator : public _STD iterator<_STD forward_iterator_tag, range_type >
    {
    public:
        typedef chunk_iterator   _Myt;

    protected:
        const Predicate&   _predicate;
        range_type _range;
        range_type _cursor;

    public:

        explicit inline chunk_iterator(const range_type& range_, const Predicate& predicate_)
            : _predicate(predicate_)
            , _range(range_)
            , _cursor(range_.first)
        {
            operator++();
        }

        chunk_iterator(const _Myt& ref_)
            : _predicate(ref_._predicate)
            , _range(ref_._range)
            , _cursor(ref_._cursor)
        {
        }

        inline _Myt& operator++() throw()
        {
            _cursor = _predicate.tokenize(_range);
            return (*this);
        }

        inline _Myt operator++(int)
        {
            _Myt tmp(*this);
            operator++();
            return tmp;
        }

        inline _Myt& operator += (size_t count_) throw()
        {
            while(count_-- && operator++())
                ;
            return (*this);
        }

        inline const range_type& operator*() const throw()
        {
            return _cursor;
        }

        inline const range_type& remaining() const throw()
        {
            return _range;
        }

        inline bool operator==(const _Myt& ref_) const throw()
        {
            return (_range == ref_._range) && (_cursor == ref_._cursor);
        }

        inline bool operator!=(const _Myt& ref_) const throw()
        {
            return !(*this == ref_);
        }

        _Myt&    reset(const range_type& range_) throw()
        {
            _range = range_;
            return operator++();
        }

        inline  operator bool() const throw()
        {
            return !(_range.empty() && _cursor.empty());
        }
    };

    typedef chunk_iterator iterator;
    typedef chunk_iterator& iterator_ref;

protected:
    const Predicate&    _predicate;
    range_type          _range;
    range_type          _end;

public:
    chunker(const Iterator begin_,
            const Iterator end_,
            const Predicate& predicate_)

        : _predicate(predicate_)
        , _range(begin_, end_)
        , _end(end_)
    {

    }

    chunker(const string_type& s_,
            const Predicate& predicate_)
        : _predicate(predicate_)
        , _range(s_.data(), s_.data()+s_.size())
        , _end(_range.second)
    {}

    chunker(const chunker& ref_)
        : _predicate(ref_._predicate)
        , _range(ref_._range)
        , _end(_range.second)
    {
    }

    inline
    chunker& operator=(const chunker& ref_)
    {
        if (this != &ref_)
        {
            _predicate = ref_._predicate;
            _range  = ref_._range;
            _end.assign(_range.second);
        }
        return *this;
    }

    inline void assign(const string_type& s_)
    {
        assign(s_.data(), s_.data()+s_.size());
    }

    inline void assign(Iterator begin, Iterator end)
    {
        _range.assign(begin_, end_);
        _end.assign(_range.second);
    }


    inline
    iterator    begin() const throw()
    {
        return (chunk_iterator(_range, _predicate));
    }

    inline
    const range_type&    end() const throw()
    {
        return _end;
    }
};


#define _DIGITS "0123456789"
#define _HEX_LETTERS_LOWER "abcdef"
#define _HEX_LETTERS_UPPER "ABCDEF"
#define _HEX_DIGITS _DIGITS _HEX_LETTERS_LOWER  _HEX_LETTERS_UPPER 
#define _LETTERS _HEX_LETTERS_LOWER _HEX_LETTERS_UPPER "ghijklmnopqrstuvwxyzGHIJKLMNOPQRSTUVWXYZ"

class   Digits : public ascii_set
{
public:
    Digits()
        : ascii_set(_DIGITS)
    {
    }
};

class   Xdigits : public ascii_set
{
public:
    Xdigits()
        : ascii_set(_HEX_DIGITS)
    {
    }
};

class   Alpha : public ascii_set
{
public:
    Alpha()
        : ascii_set(_LETTERS)
    {
    }
};

template<typename _Char>
static inline bool IsDigit(_Char _ch)
{
    static Digits digits;
    return digits.get(_ch);
}

template<typename _Char>
static inline bool IsXdigit(_Char _ch)
{
    static Xdigits digits;
    return digits.get(_ch);
}

template<typename _Char>
static inline bool IsAlpha(_Char _ch)
{
    static Alpha alpha;
    return alpha.get(_ch);
}



template <typename _CharT>
class _ptr_cch
{
public:
    typedef typename ChTraits<_CharT>            _Traits;
    typedef typename _Traits::const_pointer    const_pointer;
    typedef _ptr_cch<_CharT>            _Myt;

protected:
    const_pointer _ptr;
    size_t  _cch; 
public:
    _ptr_cch()
        : _ptr(0)
        , _cch(no_value)
    {}

    _ptr_cch(const _Myt& ref_)
        : _ptr(0)
        , _cch(no_value)
    {
        *this = ref_;
    }

    _ptr_cch(const_pointer ptr_, size_t cch_ = no_value)
        : _ptr(0)
        , _cch(no_value)
    {
        set(ptr_, cch_);
    }

    inline
    void    reset() throw()
    {
        _ptr = NULL;
        _cch = no_value;
    }

    inline  
    bool is_null() const throw()
    {
        return (_ptr == NULL);
    }

    inline 
    bool    has_size() const throw()
    {
        return (_cch != no_value);
    }

    inline
    bool    verify() const throw()
    {
        return ((is_null()) ^ (has_size()));
    }

    inline
    size_t length() const throw()
    {
        _ASSERT(verify());
        return (has_size()? _cch : 0);
    }

    inline  
    bool empty() const throw()
    {
        return (length() == 0);
    }

    inline
    void swap(_Myt& ref_) throw()
    {
        if (this != &ref_)
        {
            _STD swap(_ptr, ref_._ptr); 
            _STD swap(_cch, ref_._cch); 
        }
    }

    inline
    _Myt&   operator=(const _Myt& ref_) throw()
    {
        _ASSERT(ref_.verify());
        return set(ref_._ptr, ref_._cch);
    }

    inline
    _Myt&   operator=(const_pointer ptr_) throw()
    {
        return set(ptr_);
    }

    inline
    _Myt&    set(const_pointer ptr, size_t cch = no_value) throw()
    {
        _ptr = ptr;
        _cch = cch;
        if (!_ptr)
            _cch = no_value;
        else if (_cch == no_value)
            _cch = _Traits::length(_ptr);
        _ASSERT(verify());
        return *this;
    }

    inline
    const_pointer begin() const throw()
    {
        _ASSERT(verify());
        return (is_null()? _Traits::get_null_ptr() : _ptr);
    }

    inline
    const_pointer end() const throw()
    {
        return begin() + length();
    }

    inline
    operator const_pointer () const throw()
    {
        return begin();
    }

    inline
    size_t  min_length(const _Myt& ref_) const throw()
    {
        return _STD min(length(), ref_.length());
    }

    inline
    size_t  max_length(const _Myt& ref_) const throw()
    {
        return _STD max(length(), ref_.length());
    }

    inline
    int compare(const _Myt& ref_) const throw()
    {
        return _Traits::cmpn (begin(), ref_.begin(), max_length(ref_));
    }

    inline
    int compare_nocase(const _Myt& ref_) const throw()
    {
        return _Traits::cmpni(begin(), ref_.begin(), max_length(ref_));
    }

    inline
    bool    operator==(const _Myt& ref_) const throw()
    {
        if (length() != ref_.length())
            return false;
        return (0 == compare(ref_));
    }

    inline
    bool    operator!=(const _Myt& ref_) const throw()
    {
        return !(operator==(ref_));
    }

    inline
    bool    operator < (const _Myt& ref_) const throw()
    {
        return compare(ref_) < 0;
    }

    inline
    bool    operator <= (const _Myt& ref_) const throw()
    {
        return compare(ref_) <= 0;
    }

    inline
    bool    operator >= (const _Myt& ref_) const throw()
    {
        return compare(ref_) >= 0;
    }

    inline
    bool    operator > (const _Myt& ref_) const throw()
    {
        return compare(ref_) > 0;
    }

    inline
    const_pointer   find(_CharT ch_) const throw()
    {
        return _Traits::find(_ptr, _cch, ch_);
    }

    _Myt    get_trimmed() const throw()
    {
        const_pointer pbeg = begin();
        const_pointer pend = end();

        while(pbeg < pend && _Traits::_isspace(*pbeg))
            ++pbeg;

        while(--pend > pbeg && _Traits::_isspace(*pend))
            ;
        return _Myt(pbeg, _Traits::distance(pbeg, pend));
    }

    inline
    _Myt&    trim() throw()
    {
        return (*this = get_trimmed());
    }
};

//template<class _Ty>
//class _STD _Move_operation_category< _ptr_cch<_Ty> >
//{	// _ptr_cch implements a performant swap
//public:
//    typedef _STD _Swap_move_tag _Move_cat;
//};

template<class _Ty>
void swap(_ptr_cch<_Ty>& _1, _ptr_cch<_Ty>& _2)
{	// swap contents of _1 and _2
    _1.swap(_2);
}

template< class _Ty >
bool operator<(const _ptr_cch<_Ty>& _1,  const _ptr_cch<_Ty>& _2)
{	// return true if _1 precedes _2 
    return (_1.compare(_2) < 0);
}

template<class CharType, class Traits>
_STD basic_ostream<CharType, Traits>& operator<<(
  _STD basic_ostream<CharType, Traits>& _Ostr,
  const _ptr_cch<CharType>& _Str)
{
    return _Ostr.write(_Str.begin(), _Str.length());
}

template<class _Ty> 
inline range<const _Ty*> make_range(const _ptr_cch<_Ty>& ptr_)
{	// return range composed from arguments
    return (range<const _Ty*>(ptr_.begin(), ptr_.end()));
}


/*
   'emitter' is an utility class facilitating implementation of some string processing
   API functions wich are supposed to be called twice. the first call receives NULL as address of 
   output buffer and non-null pointer to variable of type int (charsRequired).
   emitter::write() method in this case doesn't output data but counts the number of characters 
   to output next time when the address and size of output buffer will be known 

   this class is useful when the goal of API function is to compose a string from several chunks of data
*/
template<typename _CharT>
class  emitter 
{
public:
    typedef _ptr_cch<_CharT>                    _Block_t;
    typedef typename _Block_t::_Traits          _Traits;
    typedef typename _Traits::pointer           pointer;
    typedef typename _Traits::const_pointer     const_pointer;

protected:

    pointer     _dest;
    size_t      _dest_size;
    size_t      _written;

public:
    emitter()
    {
        reset();
    }

    emitter(pointer dest_, size_t dest_size_)
        : _dest(dest_)
        , _dest_size(dest_size_)
        , _written(0)
    {
        _ASSERT(verify());
    }

    inline
    void reset()
    {
        _dest = NULL;
        _dest_size = no_value;
        _written = 0;
    }

    inline
    size_t  written() const
    {
        return _written;
    }

    inline
    bool    verify() const
    {
        return (_dest == NULL) ^ (_dest_size != no_value);
    }

    inline
    bool    empty() const
    {
        return (_dest == NULL) || (_written == 0);
    }

    int    init(pointer dest_, size_t dest_size_)
    {
        _ASSERT(verify());
        _dest = dest;
        if (_dest)
        {
            if (dest_size_ > _written)
                dest_size_ = _written;
        }
        _dest_size = dest_size_;
        _written = 0;
        _ASSERT(verify());
        return 0;
    }

    inline
    size_t    fit_size(size_t sz_)
    {
        if (_written + sz_ > _dest_size) 
        {
            _ASSERT(_written <= _dest_size);
            return _dest_size - _written;
        }
        return sz_;
    }

    size_t    write(const _Block_t& rng_)
    {
        if (!rng_.empty()) 
        {
            _ASSERT(verify());
            size_t charsToWrite = fit_size(rng_.length());
            if (charsToWrite > 0)
            {
                if (_dest != NULL) 
                {
                    _Traits::copy(_dest + _written, _dest_size-_written, rng_, charsToWrite);
                } 
                _written += charsToWrite;
            }
        }
        return _written;
    }

    inline
    size_t    write(const_pointer text_)
    {
        return write(_Block_t (text_));
    }

    size_t    write(int c)
    {
        if (_written < _dest_size) 
        {
            _ASSERT(verify());
            if (_dest != NULL) 
            {
                _CharT _ch = _Traits::to_char_type(c);
                _dest[_written] = _ch;
            } 
            ++_written;
        }
        return _written;
    }
};

template <typename _Char = char, class _Ax = _STD allocator<_Char> >
class   mini_string : protected _ptr_cch<_Char>
{
public:
    typedef _Ax _Alty;

    static __declspec(noinline)  _Alty&  get_alloc() throw()
    {
        static  _Alty  _Alloc;
        return _Alloc;
    }

    typedef _ptr_cch<_Char> _Mybase;
    typedef range<const _Char*> _Myrange;

    typedef typename _Mybase::_Traits  _Traits;
    typedef ChTraits<typename _Traits::_OtherElem>  _OtherTraits;

    typedef typename _Traits::const_pointer const_pointer; 
    typedef typename _Traits::pointer pointer; 

    typedef typename _Traits::other_const_pointer other_const_pointer; 
    typedef typename _Traits::other_pointer other_pointer; 


    typedef mini_string<_Char, _Ax> _Myt;
    typedef mini_string<typename _Traits::_OtherElem, typename _Ax::template rebind<typename _Traits::_OtherElem>::other > _Othert;
    friend _Othert;

    typedef _STD list<_Myt> _Mylist;

private:
    inline
    _Mybase*    _base_this() const
    {
        // brute cast
        union 
        {
            const _Mybase* _cptr;
            _Mybase* _ptr;

        } _ThisPtr; _ThisPtr._cptr = (this);
        return _ThisPtr._ptr;
    }

    inline
    _Mybase&    _base() const
    {
        return *_base_this();
    }

    void set(const_pointer    text_, size_t length_ = no_value)  throw()
    {
        clear();
        _Mybase::set(text_, length_);
    }

    inline
    void forget() const throw()
    {
        _base().reset();
    }

    static pointer    from_other(other_const_pointer text_, size_t  length_, size_t& out_length_) throw()
    {
        out_length_ = no_value;
        if (!text_ || !*text_)
            return (pointer)NULL;
        size_t new_length = _Traits::base_length(text_, length_);
        if (1 > (int)new_length)
        {
            return (pointer)NULL;
        }
        pointer ret = _Myt::get_alloc().allocate(new_length+1);
        if (ret)
        {
            _Traits::convert(ret, new_length+1, text_, length_);
            ret[new_length] = _OtherTraits::null;
            out_length_ = new_length;
        }
        return ret;
    }

    void set_from_other(other_const_pointer    text_, size_t length_ = no_value)  throw()
    {
        clear();
        _ptr = from_other(text_, length_, _cch);
        if (!verify())
            _cch = (_ptr == NULL )? no_value : _Traits::length(_ptr);
        if (_cch == 0)
        {
            reset();
        }
    }

public:
    mini_string()
        : _Mybase()
    {}

    mini_string(const_pointer text_, size_t length_ = no_value)  throw()
        : _Mybase()
    {
        init(text_, length_);
    }

    mini_string(const _Myrange& ref_)  throw()
        : _Mybase()
    {
        init(ref_.first, ref_.second - ref_.first);
    }

    mini_string(const _Myt& ref_)  throw()
        : _Mybase(ref_)
    {
        ref_.forget();
    }

    explicit
    mini_string(const _Mybase& ref_)  throw()
        : _Mybase()
    {
        init(ref_.begin(), ref_.length());
    }

    mini_string(const _Othert& ref_)  throw()
        : _Mybase()
    {
        _ASSERT(ref_.verify());
        init(ref_._ptr, ref_._cch);
        ref_.clear();
    }

    ~mini_string()  throw()
    {
        clear();
    }

    const _Mybase  operator*() const throw()
    {
        return (_base());
    }

    void init(const_pointer text_, size_t length_ = no_value)  throw()
    {
        clear();
        if (text_ && *text_)
        {
            if (length_ == no_value)
                length_ = _Traits::length(text_);
            _ptr = get_alloc().allocate(length_+1);
            if (_ptr)
            {
                _Traits::copy((pointer)_ptr, length_, text_, length_);
                _cch = length_;
                ((pointer)_ptr)[_cch] = _Traits::null;
            }
        }
        _ASSERT(verify());
    }

    inline
    void init(other_const_pointer text_, size_t length_ = no_value)  throw()
    {
        set_from_other(text_, length_);
        _ASSERT(verify());
    }

    inline
    void clear() const  throw()
    {
        _ASSERT(verify());
        if (_ptr)
            get_alloc().deallocate((pointer)_ptr, _cch+1);

        forget();
    }

    mini_string&    operator=(const _Myt& ref_)  throw()
    {
        if (&ref_ != this)
        {
            clear();
            _ASSERT(ref_.verify());
            _base() = ref_._base();
            ref_.forget();
        }
        return *this;
    }

    mini_string&    operator=(const _Othert& ref_)  throw()
    {
        _ASSERT(ref_.verify());
        set_from_other(ref_._ptr, ref_._cch);
        ref_.clear();
        return *this;
    }

    inline
    std::auto_ptr_ref<_Char>    detach() throw()
    {
        _ASSERT(verify());
        pointer p((pointer)_ptr);
        forget();
        return std::auto_ptr_ref<_Char>(p);
    }

    inline
    const_pointer    text() const  throw()
    {
        return begin();
    }

    inline
    operator const_pointer() const throw()
    {
        return text();
    };

    inline
    void swap(_Myt& ref_) throw()
    {
        _Mybase::swap(ref_);
    }

    inline
    int _Cmp(const_pointer p_) const throw()
    {
        return _Traits::cmp((const_pointer)*this, p_);
    }

    inline
    int _Cmpi(const_pointer p_) const throw()
    {
        return _Traits::cmpi((const_pointer)*this, p_);
    }

    inline
    operator bool() const throw()
    {
        return ToBool(_ptr && *_ptr);
    }

    inline
    bool    verify() const throw()
    {
        return _Mybase::verify();
    }

    inline
    size_t    length() const  throw()
    {
        return _Mybase::length();
    }

    inline
    bool    empty() const  throw()
    {
        return _Mybase::empty();
    }

    size_t  formatV(const_pointer format_, va_list args_) throw()
    {
        size_t flen = _Traits::formatted_length(format_, args_);
        if (flen)
        {
            _Traits::pointer txt = get_alloc().allocate(flen+1);
            _Traits::formatV(txt, flen+1, format_, args_);
            txt[flen] = _Traits::null;
            set(txt, flen);
        }
        return flen;
    }

    size_t  append_formatV(const_pointer format_, va_list args_) throw()
    {
        if (empty())
            return formatV(format_, args_);

        size_t flen = length() + _Traits::formatted_length(format_, args_);
        if (flen > _cch)
        {
            _Traits::pointer txt = get_alloc().allocate(flen+1);
            _Traits::copy(txt, _cch, _ptr, _cch);
            _Traits::formatV(txt+_cch, flen-_cch+1, format_, args_);
            txt[flen] = _Traits::null;
            set(txt, flen);
        }
        return flen;
    }

    size_t  __cdecl format(const_pointer format_, ...) throw()
    {
        va_list args;
        va_start(args, format_);
        size_t ret = formatV(format_, args);
        va_end(args);
        return ret;
    }

    size_t  __cdecl append_format(const_pointer format_, ...) throw()
    {
        va_list args;
        va_start(args, format_);
        size_t ret = append_formatV(format_, args);
        va_end(args);
        return ret;
    }

    inline
    _Myt  clone() const throw()
    {
        return (_Myt(text(), length()));
    }
};

//template<class _Ty>
//class _STD _Move_operation_category< mini_string<_Ty> >
//{	// mini_string implements a performant swap
//public:
//    typedef _STD _Swap_move_tag _Move_cat;
//};

template<class _Ty>
void swap(mini_string<_Ty>& _1, mini_string<_Ty>& _2)
{	// swap contents of _1 and _2
    _1.swap(_2);
}

template< class _Ty >
bool operator<(const mini_string<_Ty>& _1,  const mini_string<_Ty>& _2)
{	// return true if _1 precedes _2 
    return (_1._Cmp(_2) < 0);
}

template<class CharType, class Traits, class Allocator>
_STD basic_ostream<CharType, Traits>& operator<<(
  _STD basic_ostream<CharType, Traits>& _Ostr,
  const mini_string<CharType, Allocator>& _Str)
{
    return _Ostr.write(_Str.text(), _Str.length());
}

struct object
{};

struct a : public object
{};

struct b
{};

struct c : public a
{};

#include <xmemory>
typedef std::_String_const_iterator<char //, std::char_traits<char>, std::allocator<char> 
> CI;

typedef std::_String_val<char//, std::allocator<char> 
> SV;
#include <vector>

static const char str_to_tokenize[] = 
"<one>,{two}, -three- | (four) / [five] ... *six@seven%eight!nine&ten";
static const char delimiters[] = ", <>{}-|()[]/.*@%!&";
typedef _STD list<_STD basic_string<char> >  std_strlist;

size_t tokenize_cstring(const CStringA& str_, const char* delimiters_, std_strlist& out_)
{
    bitset_predicate pred;
    pred.init(delimiters_);
    range<const char*> rng(make_range(_ptr_cch<char>(str_)));
    fill<std_strlist> fl(out_);
    pred.process(fl, rng);
    //out_.clear();
    //int iStart = 0;
    //while(iStart >= 0)
    //{
    //    CStringA token = str_.Tokenize(delimiters_,iStart);
    //    if (!token.IsEmpty())
    //        out_.push_back(token);
    //}
    return out_.size();
}

#ifdef _DEBUG
#define NUM_ITERATIONS  1
#else
#define NUM_ITERATIONS  1000000 //00000
#endif
#define VALID_VALUE     10

void test_cstring()
{

    typedef _STD basic_string<char> mystr;
    //typedef _STD list<mystr>  mylist;
    mystr s(str_to_tokenize);
    bitset_predicate pred;
    pred.init(delimiters);
    range<const char*> s_rng(make_range(_ptr_cch<char>(str_to_tokenize)));
    double time(0);
    {
        scoped_timer t(time);
        for(size_t i = 0; i < NUM_ITERATIONS; ++i)
        {
            std_strlist ml;
            range<const char*> rng(s_rng);
            fill<std_strlist> fl(ml);
            pred.process(fl, rng);
            size_t n = ml.size(); //tokenize_cstring(CStringA(str_to_tokenize), delimiters, ml);
            if (n != VALID_VALUE)
            {
                _STD cout << "error in tokenize_cstring" << _STD endl;
                return;
            }
        }
    }
    _STD cout << "tokenize_cstring " << NUM_ITERATIONS << " iterations took " << time << " ticks" << _STD endl;
}

void test_mstring()
{
    typedef mini_string<char> mystr;
    mystr s(str_to_tokenize);

    bitset_predicate pred;
    pred.init(delimiters);

    double time(0);
    {
        scoped_timer t(time);
        for(size_t i = 0; i < NUM_ITERATIONS; ++i)
        {
            std_strlist ml;
            fill<std_strlist> fl(ml);
            range<const char*> rng(make_range(*s));
            pred.process(fl, rng);
            size_t n = ml.size();
            if (n != VALID_VALUE)
            {
                _STD cout << "error in tokenize_mstring" << _STD endl;
                return;
            }
        }
    }
    _STD cout << "tokenize_mstring " << NUM_ITERATIONS << " iterations took " << time << " ticks" << _STD endl;
}

void test_ptrcch()
{
    typedef _ptr_cch<char> mystr;
    mystr s(str_to_tokenize);
    bitset_predicate pred;
    pred.init(delimiters);
    double time(0);
    {
        scoped_timer t(time);
        for(size_t i = 0; i < NUM_ITERATIONS; ++i)
        {
            std_strlist ml;
            range<const char*> rng(make_range(s));
            fill<std_strlist> fl(ml);
            pred.process(fl, rng);
            size_t n = ml.size();
            if (n != VALID_VALUE)
            {
                _STD cout << "error in tokenize_ptrcch" << _STD endl;
                return;
            }
        }
    }
    _STD cout << "tokenize_ptrcch " << NUM_ITERATIONS << " iterations took " << time << " ticks" << _STD endl;
}


void test_strtk()
{
    typedef std::string mystr;
    mystr s(str_to_tokenize);
    typedef _STD list<mystr> mylist;

    strtk::multiple_char_delimiter_predicate predicate(delimiters);
    typedef strtk::std_string::tokenizer<strtk::multiple_char_delimiter_predicate>::type tokenizer_type;


    double time(0);
    {
        scoped_timer t(time);
        for(size_t i = 0; i < NUM_ITERATIONS; ++i)
        {
            mylist ml;
            std::back_insert_iterator<mylist> out(ml);
            tokenizer_type tokenizer(s,predicate,strtk::tokenize_options::compress_delimiters);
            tokenizer_type::iterator itr = tokenizer.begin();
            while (tokenizer.end() != itr)
            {
                if ((*itr).first != (*itr).second)
                    ml.push_back(mystr((*itr).first, (*itr).second));
                ++itr;
            }
            size_t n = ml.size();
            if (n != VALID_VALUE)
            {
                _STD cout << "error in tokenize_strtk" << _STD endl;
                return;
            }
            ml.clear();
        }
    }
    _STD cout << "tokenize_strtk " << NUM_ITERATIONS << " iterations took " << time << " ticks" << _STD endl;
}

void test_chunker()
{
    typedef std::string mystr;
    mystr s(str_to_tokenize);
    typedef _STD list<mystr> mylist;

    bitset_predicate predicate;
    predicate.init(delimiters);

    typedef chunker<char, bitset_predicate > tokenizer_type;
    tokenizer_type::range_type s_rng(make_range(s));

    double time(0);
    {
        scoped_timer t(time);
        for(size_t i = 0; i < NUM_ITERATIONS; ++i)
        {
            mylist ml;
            fill<std_strlist> fl(ml);
            tokenizer_type::range_type  rng(s_rng);
            predicate.process(fl, rng);
            size_t n = ml.size();
            if (n != VALID_VALUE)
            {
                _STD cout << "error in tokenize_chunker" << _STD endl;
                return;
            }
            ml.clear();
        }
    }
    _STD cout << "tokenize_chunker " << NUM_ITERATIONS << " iterations took " << time << " ticks" << _STD endl;
}

template<typename _Char>
struct  token
{
    typedef ChTraits<_Char> _Traits;
    typedef typename _Traits::const_pointer const_pointer;
    const_pointer   _text;
    int             _id;
};


template<typename _Matcher>
struct  chset // character set eg: [a-f], [^pqw], [KMGT]
{
};

template<typename _Matcher>
struct  like
{
    typedef like<_Matcher> _Myt;

    typedef _Matcher _Matcher_t;
    typedef typename _Matcher_t::_Traits _Traits;
    typedef typename _Traits::char_type _Char;
    typedef typename _Traits::cptr_range    range_type;
    typedef _STD basic_string<_Char>    _Pattern_t;

    
    _Pattern_t  _pattern;

    like(const _Pattern_t& pattern_)
        : _pattern(pattern_)
    {
        parse();
    }

    void parse(_Char escape_)
    {
    }

    void    setPattern(const _Pattern_t& pattern_, _Char escape_ = 0)
    {
        _pattern = pattern_;
        parse(escape_);
    }

    size_t  match(const range_type& text_) const
    {
        size_t ret(novalue);
        return ret;
    }
};
void test_matcher()
{
    size_t iMatchLen;
    eMatchType mt = GetMatch(_T("Abc"), _T("Abc"), iMatchLen);
    _ASSERT(mt == matchFull);

    mt = GetMatch(_T("Abc"), _T("ABD"), iMatchLen);
    _ASSERT(mt == matchPartialLeft);

    mt = GetMatch(_T("Abd"), _T("abC"), iMatchLen);
    _ASSERT(mt == matchPartialRight);

    mt = GetMatch(_T("Abc"), _T("abCD"), iMatchLen);
    _ASSERT(mt == matchLeft);

    mt = GetMatch(_T("AbCd"), _T("Abc"), iMatchLen);
    _ASSERT(mt == matchRight);

    mt = GetMatch(_T("Abde"), _T("CabC"), iMatchLen);
    _ASSERT(mt == matchNoneLeft);
    mt = GetMatch(_T("Dbde"), _T("CabC"), iMatchLen);
    _ASSERT(mt == matchNoneRight);

    mt = GetMatch(_T(""), _T("CabC"), iMatchLen);
    _ASSERT(mt == matchNone);
    mt = GetMatch(_T("CabC"), _T(""), iMatchLen);
    _ASSERT(mt == matchNone);
}
void test_matcher2()
{
    typedef matcher<char>   MyMatcher;
    typedef trie_node<MyMatcher, int>   MyTrie;

    int id(0);
    MyTrie tri;
    tri.Insert("integer", ++id);
    tri.Insert("internal", ++id);
    tri.Insert("interrupt", ++id);
    tri.Insert("int", ++id);
    tri.Insert("inline", ++id);
    tri.Insert("for", ++id);
    tri.Insert("float", ++id);
    tri.Insert("long", ++id);
    tri.Insert("const", ++id);
    tri.Insert("char", ++id);
    tri.Insert("wchar_t", ++id);
    tri.Insert("class", ++id);


    const MyTrie* found = tri.Find("float");
    found = tri.Find("auto");
    found = tri.Find("fro");
    found = tri.Find("ClaSS");
    found = tri.Find("form");
    found = tri.Find("for");
    found = tri.Find("in");
    found = tri.Find("int");
    bool b = tri.Remove("Int");
    found = tri.Find("int");
    found = tri.Find("c");
    found = tri.Find("class");
    MyTrie::cursor csr(&tri);
    
    char _word[] = "Float";
    const char* p = _word;
    while(csr.advance(*p))
        ++p;
    if (csr.completed())
        found = csr._node;
    tri.clean();
}

template <typename _Elem = unsigned char>
class   buffer {
public:
    typedef buffer<_Elem>   _Myt;
    typedef range<_Elem*>   _Range_t;
private:
    _Range_t   _block;
    _Range_t   _slide;
public:
    buffer(const _Elem*   block_, size_t size_) 
        : _block(const_cast<_Elem*>(block_), const_cast<_Elem*>(block_ + (size_ / sizeof(_Elem))))
        , _slide(_block.first)
    {

    }

    buffer(const _Myt& ref_)
        : _block(ref_._block)
        , _slide(ref_._slide)
    {
    }

    _Myt&   clear() {
        _slide.assign(block_.first);
        return *this;
    }

    size_t  capacity() const {
        return block_.length();
    }

    size_t  readAvailable() const {
        return _slide.length();
    }
    size_t  writeAvailable() const {
        return _block.second - _slide.second;
    }

    size_t  readPosition() const {
        return _slide.first - _block.first;
    }
    size_t  writePosition() const {
        return _slide.second - _block.first;
    }

    int read() {
        if (_slide.empty())
            return -1;
        _Elem val = *_slide.first; 
        ++_slide;
        return (int)val;
    }

    _Myt&   read(_Elem* dest_, size_t size_, size_t& read_) {
        size_t count = read_ = _STD min(size_, readAvailable());
        _Elem* tmp = _slide.first;
        while(0 < count--)
        {
            *dest_++ = *tmp++;
        }
        _slide.first += read_;
        return *this;
    }
    bool    write(_Elem val_) {
        if (_slide.second < _block.second) {
            *_slide.second = val_;
            _slide.grow(1);
        }
        return false;
    }

    _Myt&   write(const _Elem* data_, size_t size_, size_t& written_) {
        size_t count = written_ = _STD min(size_, writeAvailable());
        _Elem* tmp = _slide.second;
        while(0 < count--)
        {
            *tmp++ = *data_++;
        }
        _slide.grow(written_);
        return *this;
    }
};

void    test_buffer() {
    unsigned char _b[100];
    unsigned char _c[100];
    buffer<> b(_b, sizeof(_b));
    size_t written = 0,
           read = 0;
    buffer<>& ref = b.write((const unsigned char*)"abcdefg", 8, written).read(_c, sizeof(_c), read);
    _STD cout << _c << _STD endl;
    written = 0;
}
int __cdecl  _tmain(int argc, _TCHAR* argv[])
{
#if 0
    test_buffer();
#endif
#if 0
    test_matcher();
    test_matcher2();
#endif
#if 1
    //test_cstring();
    test_chunker();
    test_strtk();
    test_ptrcch();
    test_chunker();
    test_cstring();
    //test_mstring();
    test_ptrcch();
    test_strtk();
    test_chunker();
    //test_ptrcch();
    //test_mstring();
#endif

#if 0
    typedef ChTraits<char>  _CT;
    _CT ::cmpni("abc", "ABC", 3);
    _ptr_cch<char> _c1("abc");
    _ptr_cch<char> _c2("Abc");
    _c1.compare(_c2);
    _c1.compare_nocase(_c2);

    bitset_predicate d;
    *d = ascii_set("0123") + ascii_set(L"4567");
    *d += "890";
    d.add("abcdef");
    d.add(L"ABCDEF");
    const wchar_t* ppp = d.find(L"my big zoo is 1st");
    _STD wcout << ppp << _STD endl;

    bool ia = IsAlpha('a');
    ia = IsAlpha(L'b');
    ia = IsAlpha(L'0');
    ia = IsDigit('-');

    char mmmm[] = "one, two, three, four, five";
    _ptr_cch<char>  pch(mmmm);
    //_ptr_cch<char>::_Mylist lst;
    //pch.tokenize(lst, ", ");

    //for each(const _ptr_cch<char> p in lst)
    //{
    //    _STD cout << p << _STD endl;
    //}

    mini_string<> x(pch);
    _STD vector<mini_string<> > vm;
    vm.push_back("one");
    vm.push_back("two");
    vm.push_back("three");
    vm.insert(vm.begin(), "null");
    vm._Reverse(&vm[0], &vm[0]+4);
    for each(const mini_string<>& m in vm)
    {
        _STD cout << m << _STD endl;
    }
    int i = _Inherits_from<a, object>::Value;
    i = _Inherits_from<b, object>::Value;
    i = _Inherits_from<c, a>::Value;
    CI ci;
    const std::_Container_base_secure* cbs = ci._Mycont;
    mini_string<> m("my mini_string");
    mini_string<> m2(m);
    mini_string<> abc("abc");
    mini_string<> ABC(L"ABC");
    int cmpres = abc._Cmp(ABC);
    if (ABC < abc)
    {
        cmpres = abc._Cmpi(ABC);
        if (abc && !cmpres)
        {
            swap(abc, ABC);
            abc.clear();
        }
    }
    size_t ci_size = sizeof(ci);
    size_t sv_size = sizeof(SV);
    size_t ss_size = sizeof(std::string);
    m2.append_format("; sizeof(_String_const_iterator) = %d, %d, %d, %d", sizeof(CI), sv_size, ci_size, ss_size);
    //mini_string<>::_Mylist lstlst;
    //m2.tokenize("()=, ", lstlst);
    _ptr_cch<char> pm2 = *m2;
    (*m2).compare(", "); //tokenize
    mini_string<wchar_t> wm;
    wm = m2;
    bool is = mini_string<wchar_t>::_Traits::_isalpha(L'?');
    wm.format(L"mini_string<wchar_t> is of size %d bytes, contains text[%s]\n", sizeof(mini_string<wchar_t>), wm.text());
    range<const wchar_t*> ident = get_ident<wchar_t>(::make_range(*wm));
    std::wcout << "[" << ident << "]" << std::endl;
    mini_string<char> am(wm.text());
    std::cout << am.text() << ",,,," << std::endl;
    std::wcout << (LPCWSTR)wm << L"...\n" << L'\r' << L'\n';
    std::wcout.flush();
    mini_string<char> m3("no_msg");
    m3.format("%s : %s", __FUNCTION__, "no error");
    mini_string<char> m4 = m2.clone();
    if (m4._Cmp(m2))
    {
        m2.clear();
    }
    m4.append_format("(append %s, %s)", m4.text(), m4.text());
    m4 = m3.clone();
    m3 = m2;
    bool b = m3.verify();
    b = m2.verify();
    b = m.verify();
    std::auto_ptr<char> atext = m3.detach();
    atext.reset();
    m.format("[%s]", atext.get());
    std::string s(m);
    m4 = mini_string<char>(s.c_str());

    emitter<char> em;
    em.write("adfasd");
    em.write('C');
    em.write(*ABC);
    
    _STD cout << "Characters reqd = " << em.written() << _STD endl;
#endif
	return 0;
}

#if 0

unsigned long long gcd(unsigned long long a, unsigned long long b)
{
    if(b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

unsigned long long r(unsigned long long x, unsigned long long N)
{
    return ((x * x) + 1) % N;
}

void prho(unsigned long long n)
{
    unsigned long long e = 0, trials = 0, p = 0, q = 0, d = 0, n2 = 2 * n + 1;
    unsigned long long x = 2, y = 2;
    srand(time(0));

    while(true) {
        trials++;
        x = r(x,n);
        y = r(r(y,n),n);

        // printf("trials=%lld\tx=%lld\ty=%lld\n",trials,x,y);
        if((d=gcd(abs(x-y),n)) != 1 && d != n) {
            p = d;
            q = n / p;
            printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",e,p,q,trials);
            return;
        }
        if( d == n) {
            printf("failed: f=f f=f f=f f=f\n");
            return;
        }
    }
}

bool is_prime(unsigned long long i)
{
    if ((i % 2) == 0) {
        return false;
    }
    unsigned long long t = (unsigned long long)ceil(sqrt(i));
    for(unsigned long long j = 3; j < t; j += 2) {
        if((i % j) == 0) {
            return false;
        }
    }
    return true;
}

unsigned long long maxGB(unsigned long long i)
{
    unsigned long long t = i / 2, s = t;
    while(t) {
        t--;
        s++;
        if(is_prime(t) && is_prime(s) && ((s + t) == i)) {
            return t * s;
        }
    }
    return 0;
}

bool Q(unsigned long long n, unsigned long long e, unsigned long long *p, unsigned long long *q)
{
    unsigned long long p_q = (unsigned long long)sqrt((e * e) - (4 * n));
    *p = (e - p_q) / 2;
    *q = (e + p_q) / 2;
    if((*p * *q) == n) {
        return true;
    }
    return false;
}

unsigned long long f(unsigned long long n, unsigned long long min, unsigned long long max)
{
    unsigned long long e = 0, p = 0, q = 0, p_e = 0;
    if((min%2)) { min++; }
    if((max%2)) { max++; }
    while(min < max) {
        e = (min + max) / 2;
        if((e % 2) == 1) e++;
        if(p_e == e) {
            // printf("%d\n",e);
            return e;
        }
        if(maxGB(e) > n) {
            max = e - 1;
        }
        if(maxGB(e) < n) {
            min = e + 1;
        }
        if(maxGB(e) == n) {
            Q(n,e,&p,&q);
            // printf("e=%d\tp=%d\tq=%d\n",e,p,q);
            return e;
        }
        if(Q(n,e,&p,&q)) {
            // printf("e=%d\tp=%d\tq=%d\n",e,p,q);
            return e;
        }
        p_e = e;
    }
    // printf("%d\n",e);
    return e;
}

void f2(unsigned long long n)
{
    unsigned long long e = f(n,2,n+1), p = 0, q = 0, trials = 0;
    if(Q(n,e,&p,&q)) {
        printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",e,p,q,trials);
        return;
    } else {
        printf("starting e=%lld\n",e);
        e += 16000;
        for(unsigned long long i = e; i < (e + 30000); i+=2, trials++) {
            if(Q(n,i,&p,&q)) {
                printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",i,p,q,trials);
                return;
            }
        }
        for(unsigned long long i = e; i >= 0; i-=2, trials++) {
            if(Q(n,i,&p,&q)) {
                printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",i,p,q,trials);
                return;
            }
        }
        for(unsigned long long i = e; i < (n + 1); i+=2, trials++) {
            if(Q(n,i,&p,&q)) {
                printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",i,p,q,trials);
                return;
            }
        }

    }
    printf("failed\n");
}


void f1(unsigned long long n)
{
    unsigned long long e = f(n,2,n+1), p = 0, q = 0, trials = 0;
    if(Q(n,e,&p,&q)) {
        printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",e,p,q,trials);
        return;
    } else {
        // printf("starting e=%lld\n",e);
        for(unsigned long long i = e; i < (n + 1); i+=2, trials++) {
            if(Q(n,i,&p,&q)) {
                printf("belowfactored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",i,p,q,trials);
                return;
            }
        }
        for(unsigned long long i = e; i >= 0; i-=2, trials++) {
            if(Q(n,i,&p,&q)) {
                printf("abovefactored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",i,p,q,trials);
                return;
            }
        }
    }
    printf("failed\n");
}

typedef struct arg {
    unsigned long long e;
    unsigned long long end;
    unsigned long long n;
    arg(unsigned long long _e,
        unsigned long long _end,
        unsigned long long _n)
        : e(_e), end(_end), n(_n)
    {
    }
} arg_t;

void *worker_thread(void *args)
{
    arg_t *a = (arg_t *)args;
    unsigned long long trials = 0;
    unsigned long long p = 0, q = 0;
    for(unsigned long long i = a->e; i < a->end; i+=2, trials++) {
       if(Q(a->n,i,&p,&q)) {
          printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",i,p,q,trials);
          exit(0); 
       }
    }
    return NULL;
}

#define NR_THREADS 16
void f3(unsigned long long n)
{
    unsigned long long e = f(n,2,n+1), p = 0, q = 0, trials = 0;
    // printf(" approximated e=%lld\n",e);
    if(Q(n,e,&p,&q)) {
        printf("factored: e=%lld\tp=%lld\tq=%lld\ttrials=%lld\n",e,p,q,trials);
        return;
    } else {
        // unsigned long long quantum = (n - e) / (NR_THREADS - 1);
        unsigned long long quantum = 20000;
        pthread_t threads[NR_THREADS]={0};
        // printf("quantum=%lld e=%lld n=%lld\n",quantum,e,n);
        for(int nr_threads = 0; nr_threads < NR_THREADS; nr_threads++) {
            arg_t *a = new arg_t(e + (nr_threads * quantum), n + 1, n);
            pthread_create(&threads[nr_threads], NULL, worker_thread, (void *)a);
        }
        for(int nr_threads = 0; nr_threads < NR_THREADS; nr_threads++) {
            pthread_join(threads[nr_threads], NULL);
        }
    }
    printf("failed\n");
}

int
main(int argc, char **argv)
{
    if(argc != 2) {
        fprintf(stderr, "usage: t n\n");
        return 1;
    }
    unsigned long long n = strtoull(argv[1],NULL,10);
    f3(n);
}
#endif

#if 0
template <typename _Char = char>
class   messages
{
public:
    typedef mini_string<_Char>          _Message_t;
    typedef _STD list<_Message_t>   _List_t;

private:
    _List_t     _list;
public:
    messages()
    {
    }
    ~messages()
    {
    }
};

enum ErrorDomain
{
    NONE            = -1,
    ARGUMENTS		= (int) 'a',
    CONVERSION		= (int) 'c',
    COMPRESSION		= (int) 'C',
    ENCRYPTION		= (int) 'E',
    IO			    = (int) 'I',
    //INPUT			= (int) 'i',
    MEMORY			= (int) 'm',
    OUTPUT			= (int) 'o',
    RUNTIME			= (int) 'r',
};


#define BIND_CODE(domain_value, code_type) \
    typedef struct error_code<domain_value, code_type, (code_type)-1> _code_##code_type;




enum ARGUMENT_ERROR
{
    argerr_NONE            = -1,

	argerr_GENERIC			= 0,

	/* The argument contains an invalid value
	 */
	argerr_INVALID_VALUE		= 1,

	/* The argument contains a value less than zero
	 */
	argerr_VALUE_LESS_THAN_ZERO	= 2,

	/* The argument contains a value zero or less
	 */
	argerr_VALUE_ZERO_OR_LESS	= 3,

	/* The argument contains a value that exceeds the maximum
	 * for the specific type
	 */
	argerr_VALUE_EXCEEDS_MAXIMUM	= 4,

	/* The argument contains a value that is too small
	 */
	argerr_VALUE_TOO_SMALL		= 5,

	/* The argument contains a value that is too large
	 */
	argerr_VALUE_TOO_LARGE		= 6,

	/* The argument contains a value that is out of bound
	 */
	argerr_VALUE_OUT_OF_BOUNDS	= 7,

	/* The argument contains a value that is not supported
	 */
	argerr_UNSUPPORTED_VALUE	= 8,

	/* The argument contains a value that conficts with another argument
	 */
	argerr_CONFLICTING_VALUE	= 9
};

enum CONVERSION_ERROR
{
    converr_NONE            = -1,
	converr_GENERIC		= 0,

	/* The conversion failed on the input
	 */
	converr_INPUT_FAILED		= 1,

	/* The conversion failed on the output
	 */
	converr_OUTPUT_FAILED		= 2
};

/* The compression error codes
 * to signify errors regarding compression
 */
enum COMPRESSION_ERROR //: short
{
    comprerr_NONE        = (short)-1,
	comprerr_GENERIC		= 0,

	/* The compression failed
	 */
	comprerr_COMPRESS_FAILED	= 1,

	/* The decompression failed
	 */
	comprerr_DECOMPRESS_FAILED	= 2
};


template <typename _Domain>
class   error_info
{
public:
    typedef _Domain _domain_t;
protected:
    _domain_t _domain;
    int     _code;
public:
    error_info(_domain_t domain_, int code_)
        : _domain(domain_)
        , _code(code_)
    {}

    error_info& operator=(const error_info& ref_)
    {
        _domain = ref_._domain;
        _code = ref_._code;
        return *this;
    }
    inline
    _domain_t domain() const throw()
    {
        return _domain;
    }

    inline
    int code() const throw()
    {
        return _code;
    }
};


template <typename _Domain, const typename _Domain null_value = (typename _Domain)-1>
struct err_builder_base
{
    typedef typename _Domain _domain_t;
    enum    no_error_enum
    {
        _no_error = -1
    };

    template <const _domain_t domain_value, typename code_type, const typename code_type null_code = (typename code_type)-1>
    struct  error_code
    {
        typedef typename code_type  type;
        static const type _null  = null_code;
    };

    //template <>
    //struct  error_code<null_value, no_error_enum>
    //{
    //    typedef no_error_enum  type;
    //    static const type _null  = _no_error;
    //};
};

struct  err_builder : public err_builder_base<ErrorDomain, NONE>
{
    BIND_CODE(ARGUMENTS, ARGUMENT_ERROR)
    BIND_CODE(CONVERSION, CONVERSION_ERROR)
    BIND_CODE(COMPRESSION, COMPRESSION_ERROR)
};

struct error_saver
{
	/* The error domain
	 */
	int domain;

	/* The error code
	 */
	int code;

	///* The number of messages
	// */
	//int number_of_messages;

	///* A dynamic array containing the mini_string strings
	// */
	//libcstring_system_character_t **messages;

	///* A dynamic array containing the mini_string string lengths
	// * without the end-of-string character
	// */
	//size_t *lengths;
};

#include <string>
#include <map>
#include <cassert>
// Helper macros

#define Begin_Enum_String(EnumerationName)                                      \
    template <> struct EnumString<EnumerationName> :                            \
        public EnumStringBase< EnumString<EnumerationName>, EnumerationName >   \
    {                                                                           \
        static void RegisterEnumerators()
//      {

#define Enum_String(EnumeratorName)                                             \
            RegisterEnumerator( EnumeratorName, #EnumeratorName );
//      }

#define End_Enum_String                                                         \
    }

// The EnumString base class
template <class DerivedType, class EnumType>
class EnumStringBase
{
// Types
protected:
    typedef std::map<std::string, EnumType> AssocMap;

protected:
// Constructor / Destructor
    explicit EnumStringBase();
    ~EnumStringBase();

private:
// Copy Constructor / Assignment Operator
    EnumStringBase(const EnumStringBase &);
    const EnumStringBase &operator =(const EnumStringBase &);

// Functions
private:
    static AssocMap &GetMap();

protected:
    // Use this helper function to register each enumerator
    // and its string representation.
    static void RegisterEnumerator(const EnumType e, const std::string &eStr);

public:
    // Converts from an enumerator to a string.
    // Returns an empty string if the enumerator was not registered.
    static const std::string &From(const EnumType e);

    // Converts from a string to an enumerator.
    // Returns true if the conversion is successful; false otherwise.
    static const bool To(EnumType &e, const std::string &str);
};

// The EnumString class
// Note: Specialize this class for each enumeration, and implement
//       the RegisterEnumerators() function.
template <class EnumType>
struct EnumString : public EnumStringBase< EnumString<EnumType>, EnumType >
{
    static void RegisterEnumerators();
};

// Function definitions

template <class D, class E>
typename EnumStringBase<D,E>::AssocMap &EnumStringBase<D,E>::GetMap()
{
    // A static map of associations from strings to enumerators
    static AssocMap assocMap;
    static bool     bFirstAccess = true;

    // If this is the first time we're accessing the map, then populate it.
    if( bFirstAccess )
    {
        bFirstAccess = false;
        D::RegisterEnumerators();
        assert( !assocMap.empty() );
    }

    return assocMap;
}

template <class D, class E>
void EnumStringBase<D,E>::RegisterEnumerator(const E e, const std::string &eStr)
{
    const bool bRegistered = GetMap().insert( typename AssocMap::value_type( eStr, e ) ).second;
    assert( bRegistered );
    (void)sizeof( bRegistered ); // This is to avoid the pesky 'unused variable' warning in Release Builds.
}

template <class D, class E>
const std::string &EnumStringBase<D,E>::From(const E e)
{
    for(;;) // Code block
    {
        // Search for the enumerator in our map
        typename AssocMap::const_iterator i;
        for(i = GetMap().begin(); i != GetMap().end(); ++i)
            if( (*i).second == e )
                break;

        // If we didn't find it, we can't do this conversion
        if( i == GetMap().end() )
            break;

        // Keep searching and see if we find another one with the same value
        typename AssocMap::const_iterator j( i );
        for(++j; j != GetMap().end(); ++j)
            if( (*j).second == e )
                break;

        // If we found another one with the same value, we can't do this conversion
        if( j != GetMap().end() )
            break;

        // We found exactly one string which matches the required enumerator
        return (*i).first;
    }

    // We couldn't do this conversion; return an empty string.
    static const std::string dummy;
    return dummy;
}

template <class D, class E>
const bool EnumStringBase<D,E>::To(E &e, const std::string &str)
{
    // Search for the string in our map.
    const typename AssocMap::const_iterator itr( GetMap().find( str ) );

    // If we have it, then return the associated enumerator.
    if( itr != GetMap().end() )
    {
        e = (*itr).second;
        return true;
    }

    // We don't have it; the conversion failed.
    return false;
}

#endif